package leetcode.tree;

import java.util.HashSet;

/**
 * @author wangmaolin1
 * @date 2023/11/12 21:42
 */
public class _1676 {
    TreeNode lowestCommonAncestor(TreeNode root, TreeNode[] nodes) {
        // 将列表转化成哈希集合，便于判断元素是否存在
        HashSet<Integer> values = new HashSet<>();
        for (TreeNode node : nodes) {
            values.add(node.val);
        }

        return find(root, values);
    }

    private TreeNode find(TreeNode root, HashSet<Integer> values) {
        if (root == null) {
            return null;
        }
        if (values.contains(root.val)) {
            return root;
        }
        TreeNode left = find(root.left, values);
        TreeNode right = find(root.right, values);
        if (left != null && right != null) {
            return root;
        }
        return left == null ? right : left;
    }

}
